public class Solution79 {
    /**
     * 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
     * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，
     * 其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
     * <p>
     * 示例:
     * <p>
     * board =
     * [
     * ['A','B','C','E'],
     * ['S','F','C','S'],
     * ['A','D','E','E']
     * ]
     * <p>
     * 给定 word = "ABCCED", 返回 true.
     * 给定 word = "SEE", 返回 true.
     * 给定 word = "ABCB", 返回 false.
     */
    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        if (rows == 0) {
            return false;
        }
        int cols = board[0].length;
        boolean[][] help = new boolean[rows][cols];
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (existCore(board, row, col, rows, cols, word, 0, help)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean existCore(char[][] board, int row, int col, int rows, int cols, String word, int index, boolean[][] help) {
        if (index == word.length()) {
            return true;
        }
        if (row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] != word.charAt(index) || help[row][col]) {
            return false;
        }
        help[row][col] = true;
        boolean result = existCore(board, row + 1, col, rows, cols, word, index + 1, help) ||
                existCore(board, row - 1, col, rows, cols, word, index + 1, help) ||
                existCore(board, row, col + 1, rows, cols, word, index + 1, help) ||
                existCore(board, row, col - 1, rows, cols, word, index + 1, help);
        help[row][col] = false;
        return result;
    }
}
